The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. IP forwarding requires a longest prefix match.
Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, and associative memories, including, but not limited to binary content-addressable memories (binary CAMs) and ternary content-addressable memories (ternary CAMs or TCAMs). Each entry of a binary CAM typically includes a value for matching against, while each TCAM entry typically includes a value and a mask. The associative memory compares a lookup word against all of the entries in parallel, and typically generates an indication of the highest priority entry that matches the lookup word. An entry matches the lookup word in a binary CAM if the lookup word and the entry value are identical, while an entry matches the lookup word in a TCAM if the lookup word and the entry value are identical in the bits that are not indicated by the mask as being irrelevant to the comparison operations.
FIGS. 1A-B illustrate one implementation of a prior art binary content-addressable memory entry 100 and bit cells 101A-B therein. Each bit cell 101A-B includes a storage 105A-B for storing a value to be matched against, which are stored by exerting the read/write line 110 and based on the bit values and their complements on lines 111A-B and 112A-B. In order to determine if binary content-addressable memory entry 100 matches a lookup word, match line 132 is precharged to Vdd based on precharging signal 120 during a precharging phase of the lookup operation. The bit values (and their complements) of the lookup word are applied on bit lines 111A-B and 112A-B, which are compared by comparison circuits 130 during a matching phase of the lookup operation to the stored bit values (105A-B). If any of the entry bit cells 101A-B determine that they do not match, then match line 132 is discharged by the corresponding comparison circuit(s) 130.
This is shown in more depth in FIG. 1B by binary CAM cell 140 with discharge paths 141. The particular one of the two discharge paths 141 that will discharge match line 132 in response to an input bit value not matching the stored value depends on the stored value to be matched, the input bit's lookup value, and the implementation of the binary CAM cell.
Any drop in the voltage of match line 132 is amplified, with any slight change in the voltage of match line 132 quickly detected by match line sense amplifier 135, which provides the corresponding hit/miss indication 136 based on the results of the comparison operations.
FIGS. 1C-D illustrate one implementation of a prior art ternary content-addressable memory entry 150 and bit cells 151A-B therein. The operation of ternary CAM entry 150 is very similar to that of binary CAM entry (FIG. 1A). Each TCAM cell A-B stores a value to be matched against, with this value representing one of the three values: one, zero and don't care/wild card (i.e., match either one or zero). Therefore, a two-bit storage 155A-B is typically used in TCAM cells 151A-B to store its value. Any drop in the voltage of match line 182 caused by comparison circuits 180 is amplified, with any slight change in the voltage of match line 182 quickly detected by match line sense amplifier 185, which provides the corresponding hit/miss indication 186 based on the results of the comparison operations.
For example, in a TCAM cell, a stored value of one might be encoded as bits ‘10’, a zero might be encoded as bits ‘01’, and don't care (often represented as ‘*’) might be encoded as bits ‘00’. The encoding of the bits to be matched are supplied via data lines 161A-B and 162A-B. With this encoding scheme for storing the values in TCAM cells 151A-B and the NMOS implementation shown in more detail in FIG. 1D, an encoding of the lookup value of one or zero for each TCAM cell is just such that if the supplied lookup bit value does not match the TCAM cell 190, then one of the two discharge paths 191 will be turned on to pull down match line 182. For example, with a stored value of one (‘10’), a supplied lookup value of zero (‘10’) is provided such that two transistors will be enabled to form one of the discharge paths 191, causing match line 182 to drop. This voltage drop is detected by match line sense amplifier 185 and a miss signal 186 generated to signal that the stored value in the TCAM entry does not match the lookup word. Note, if the encoding of a don't care value is ‘00’ and each bit is applied to a transistor in a different discharge path, then a discharge path will never become active, and therefore, the TCAM cell will effectively match the value of the corresponding bit of the lookup word.
Associative memories are very useful in performing packet classification operations. As with most any system, errors can occur. For example, array parity errors can occur in certain content-addressable memories as a result of failure-in-time errors which are typical of semiconductor devices.
When a packet classification lookup operation is performed on an associative memory with corrupted entries, a bit error in an entry can result in a false hit, or a false miss. A false hit occurs when the corrupted value of an entry matches the lookup value when it otherwise would not match that entry (and thus another entry or no entry should have been matched). A false miss occurs when an entry should have been matched except for the corruption in the entry. This could result in no entry being matched or another lower-priority entry being matched. When these lookup operations are used for packet classification, an incorrect match or miss presents a problem especially when identifying a route or performing a security classification.
Error-correcting and error-detecting codes are well-known. For example, ANDREW S. TANENBAUM, COMPUTER NETWORKS, Prentice-Hall, 1981, pp. 125-132, discusses error-correcting and error-detecting codes, and is hereby incorporated by reference. Assume a codeword contains n bits of which m are data bits and r are error-correcting or error-detecting bits (e.g., redundant or check bits), with n=m+r. There are many well-known ways to generate the error-detecting and error-correcting bits. Given two codewords, it is possible to determine how many bits differ (e.g., by exclusively-OR'ing or one bit summing the corresponding bits of the two codewords and summing these results). The number of bit positions in which two codewords or a set of codewords differ is called the Hamming distance. A Hamming distance of d, means that it will require d single-bit errors to convert one codeword to another codeword. To detect j errors, a Hamming distance of j+1 is required because with such a code, there is no way that j single-bit errors can change a valid codeword into another valid codeword. Similarly, to correct j errors, a distance 2j+1 code because that way the legal codewords are so far apart that even with j changes, the original codeword is still closer than any other codeword, so it can be uniquely determined.
A prior approach protects the associative memory entries with error detection or correction values when the associative memory is not being used to perform a lookup operation. For example, using a background operation, the associative memory entries are periodically checked and corrected for errors (e.g., read from their location and if an error, the correct value is written back). Another prior approach is to periodically over write each associative memory entry with the correct value. These and other prior approaches do not immediately detect the error, nor detect the error when a lookup operation is performed on the corrupted entry. Thus, there can be significant periods (e.g., several seconds to minutes which can be a very long time in the context of a packet switch) before such corrupted entry is corrected.
Some random access memory (RAM) add error-correcting or error-detecting codes to each memory cell. As part of a read operation of a memory location, the data portion and the error-correcting or error-detecting code is read, which is then used to detect a possible error and/or correct a discovered error in the data portion. This is especially convenient to do as only one set of error-detecting/error correcting circuitry is required (i.e., to operate on the data read from the specified memory location). However, this approach is impractical for an associative memory, as each associative memory entry would need this complete circuitry, and the result of the error-corrected operation for each memory location would need to be compared to the lookup word for every lookup operation.
Shoham et al., “Error Protection for Lookup Operations in Content-Addressable Memory Entries,” U.S. patent application Ser. No. 10/879,254, filed Jun. 29, 2004, is hereby incorporated by reference in its entirety. Shoham et al. discloses techniques for populating content-addressable memory entries with values that have a Hamming distance of n bits and for identifying a matching entry that matches in at least k bit positions, where n>k>0. Other techniques not explicitly disclosed in Shoham et al. for identifying such matching entries could be useful.
Routers typically use TCAMs for identifying routing information as they are efficient at determining a longest matching prefix on an IP route, for example; while bridges typically use a CAM for identifying routing information as they are efficient at determining an exact match on a frame address, for example. Of course, a TCAM can perform CAM lookup operations (e.g., by not programming don't care cases and therefore an exact match is required), but each TCAM cell typically requires substantially more space and may consume more power than a standard CAM cell.